Skip to content

Leetcode 45. Jump Game II 题解

题目链接

Leetcode 45. Jump Game II

题目内容

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example: Input: [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

解题思路

这题是我这周从leetcode上随便找的一题hard难度的题目。看到题目我一开始想到的就是通过BFS来解决这个问题，通过我们熟悉的BFS完成深搜，我们很容易就可以解决这个问题，但是，提交之后发现使用BFS时间复杂度较高，仅仅比37.07%的使用CPP的AC提交要快，所以我后来想到了另一种不太严格的贪心算法。 1

第二个算法主要的思想就是，只用一次遍历(O(n))，通过在遍历中不断维护ans(当前步数)，last(前一步跳跃达到的最远范围)，cur(当前跳一步可以达到的最远范围)这三个变量，使得可以判断每一步可以达到的范围和下一步可达到的最大范围，一旦遍历到的i大于上一步的最大范围，但是是这一步可以达到的范围，则跳跃，更新ans, last = cur, 并继续维护cur为当前跳一步可以达到的最大范围，直到遍历到最后一个index。当我们遍历到最后一个index，我们就可以知道index在第几步的范围内，即我们最少需要几步达到last index.第二种解法的Detail如下 2

题目代码

BFS方法

class Solution {
public:
    int jump(vector<int>& nums) {
        int size = nums.size();
        if (size == 1)
            return 0;
        vector<int> result(nums.size() - 1, -1);
        queue<int> tmpData;
        result[0] = 0;
        tmpData.push(0);
        while(!result.empty()) {
            int tmp = tmpData.front();
            tmpData.pop();
            for (int i = nums[tmp]; i > 0; i--) {
                if (tmp + i >= size)
                    continue;
                if (tmp + i == size - 1)
                    return result[tmp] + 1;
                if (result[tmp + i] < 0) {
                    result[tmp + i] = result[tmp] + 1;
                    tmpData.push(tmp + i);
                }
            }
        }
        return -1;
    }
};

不严格的贪心算法

class Solution {
public:
    int jump(vector<int>& nums) {
        int ans = 0;
        int size = nums.size();
        int last = 0;//上一跳为止可达最远距离
        int cur = 0;//当前可达最远距离
        for (int i = 0; i < size; ++i) {
            if(i > cur){
                return -1;
            } // 当前最远距离无法跳到i直接返回-1
            if (i > last) {
                last = cur;
                ++ans;
            } // i > last表示上一步jump到达的范围已经无法包含i,需要进行一次跳跃以更新last和ans,即更新当步可以跳到的范围以包含i
            cur = max(cur, i + nums[i]);//记录当前可达的最远点
        }
        return ans;
    }
};